// 1. 如果第一个格点 obstacleGrid[0,0] 是 1，说明有障碍物，那么机器人不能做任何移动，我们返回结果 0。
// 2. 否则，如果 obstacleGrid[0,0] 是 0，我们初始化这个值为 1 然后继续算法
// 3. 遍历第一行，如果有一个格点初始值为 1 ，说明当前节点有障碍物，没有路径可以通过
// 设值为 0 ；否则设这个值是前一个节点的值 obstacleGrid[i,j] = obstacleGrid[i,j-1]
// 4. 遍历第一列，如果有一个格点初始值为 1 ，说明当前节点有障碍物，没有路径可以通过
// 设值为 0 ；否则设这个值是前一个节点的值 obstacleGrid[i,j] = obstacleGrid[i-1,j]
// 5. 现在，从 obstacleGrid[1,1] 开始遍历整个数组，如果某个格点初始不包含任何障碍物
// 就把值赋为上方和左侧两个格点方案数之和 obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]。
// 6. 如果这个点有障碍物，设值为 0 ，这可以保证不会对后面的路径产生贡献

// 网格中的障碍物和空格用 1 和 0 来表示

var uniquePathsWithObstacles = function (obstacleGrid) {
  // 行
  let m = obstacleGrid.length;
  // 列
  let n = obstacleGrid[0].length;
  // 初始化
  let dp = new Array(m);
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(0);
  }

  // 如果起点就是障碍物
  dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
  if (dp[0][0] == 0) {
    return 0;
  }

  // 第一行
  for (let j = 1; j < n; j++) {
    if (obstacleGrid[0][j] !== 1) {
      dp[0][j] = dp[0][j - 1];
    }
  }

  // 第一列
  for (let i = 1; i < m; i++) {
    if (obstacleGrid[i][0] !== 1) {
      dp[i][0] = dp[i - 1][0];
    }
  }

  // 动态递归
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j] !== 1) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }

  return dp[m - 1][n - 1];
};
